import org.junit.Test;
import static org.junit.Assert.*;
import java.util.Random;
public class PrimeTest
{
	@Test
	public void testFun()
	{
		int m=15,n=20;
		int r=prime(m,n);
		assertEquals(5,r);

		m=17*2;
		n=31*2;
		r=prime(m,n);
		assertEquals(2,r);

		int a=2,b=3;
		a^=b;b^=a;a^=b;
		assertEquals(3,a);
		assertEquals(2,b);
		int[] result=prime1(m,n);
		assertEquals(2,result[0]);
		assertEquals(2,result[1]*m+result[2]*n);

		int testCount=10;
		while(testCount>0)
		{
			m=(int)(Math.random()*10000);
			n=(int)(Math.random()*10000);
			result=prime1(m,n);
			assertEquals(prime(m,n),result[0]);
			assertEquals(prime(m,n),result[1]*m+result[2]*n);
			testCount--;
		}
	}	
	int prime(int c,int d)
	{
		while(true)
		{
			if(c==0||d==0)break;
			if(c>d)c%=d;
			else d%=c;
		}
		if(c==0)return d;
		else return c;
	}
	/*[0] is gcd,[1]c+[2]d=gcd*/
	int[] prime1(int m,int n)
	{
		int a0=0,b0=1,a=1,b=0,c=m,d=n,q=0,r=0;
		if(c<d){c^=d;d^=c;c^=d;}//exchange
		while(true)
		{
			if(d==0)break;//loop invariance : a*m+b*n=c,a0*m+b0*n=d
			q=c/d;
			r=c-q*d;
			c=d;
			d=r;
			int tempa=a,tempb=b;
			a=a0;
			b=b0;
			a0=tempa-a0*q;
			b0=tempb-b0*q;
		}
		int[] result=new int[3];
		result[0]=c;
		if(m>n)
		{
			result[1]=a;
			result[2]=b;
		}
		else
		{
			result[1]=b;
			result[2]=a;
		}
		return result;
	}
}
